// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.
//原本的bcache,所有的buffer都被组织到 一条链表中，
//因此如果有多个进程要使用buffer，它们并发的请求只能被顺序地处理。
//使用哈希表进行优化。
#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"



#define NBUCKET 13//哈希桶的数量

struct
{
  struct spinlock lock[NBUCKET];
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf hashtable[NBUCKET];
} bcache;

void binit(void)
{
  struct buf *b;
  int i = 0;

  for (i = 0; i < NBUCKET; i++)
  // Create linked list of buffers
  {
    initlock(&bcache.lock[i], "bcache");//将哈希表中每一个bucket lock 初始化，自旋锁bcache[i].lock用于用户互斥访问。
    bcache.hashtable[i].prev = &bcache.hashtable[i];
    bcache.hashtable[i].next = &bcache.hashtable[i];
  }

  i = 0;
  for (b = bcache.buf; b < bcache.buf + NBUF; b++)
  {
    b->next = bcache.hashtable[i].next;
    b->prev = &bcache.hashtable[i];
    initsleeplock(&b->lock, "buffer");
    bcache.hashtable[i].next->prev = b;
    bcache.hashtable[i].next = b;
  }
  
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
//查找缓存块
static struct buf *
bget(uint dev, uint blockno)
{
  struct buf *b;
  int no = blockno % NBUCKET;//组号
  acquire(&bcache.lock[no]);
  // Is the block already cached?
  for (b = bcache.hashtable[no].next; b != &bcache.hashtable[no]; b = b->next)
  {
    if (b->dev == dev && b->blockno == blockno)
    {
      b->refcnt++;
      
      release(&bcache.lock[no]);
      acquiresleep(&b->lock);
      return b;
    }
  }
  int i = 0;
  //从其他哈希桶选择一个未被使用的缓存块，移入到以blockno为key的哈希组链表中使用。
  for (i = (no + 1)%NBUCKET; i != no; i = (i + 1)%NBUCKET)
  
  {
    //为未命中的缓存分配一个新的条目,原子性操作要加锁
    acquire(&bcache.lock[i]);
    for (b = bcache.hashtable[i].prev; b != &bcache.hashtable[i]; b = b->prev)
    {
      if (b->refcnt == 0 )
      {
        
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;//即该buffer不包含对应磁盘块的数据
        b->refcnt = 1;
        b->next->prev = b->prev;
        b->prev->next = b->next;

        b->next = bcache.hashtable[no].next;
        b->prev = &bcache.hashtable[no];
        bcache.hashtable[no].next->prev = b;
        bcache.hashtable[no].next = b;
        release(&bcache.lock[i]);
        release(&bcache.lock[no]);
        acquiresleep(&b->lock);
        return b;
      }
      
    }
    release(&bcache.lock[i]);
  }
  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.

struct buf *
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if (!b->valid)
  {
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
//将缓存块写入磁盘
void bwrite(struct buf *b)
{
  if (!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b, 1);
}

// Release a locked buffer.
// Move to the head of the most-recently-used list.
//释放缓存块
void brelse(struct buf *b)
{
  if (!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&bcache.lock[b->blockno % NBUCKET]);
  b->refcnt--;
  if (b->refcnt == 0)
  {
    //no one is waiting for it.
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.hashtable[b->blockno % NBUCKET].next;
    b->prev = &bcache.hashtable[b->blockno % NBUCKET];
    bcache.hashtable[b->blockno % NBUCKET].next->prev = b;
    bcache.hashtable[b->blockno % NBUCKET].next = b;
  }
  release(&bcache.lock[b->blockno % NBUCKET]);
}
//引用缓存块
void bpin(struct buf *b)
{
  acquire(&bcache.lock[b->blockno % NBUCKET]);
  b->refcnt++;
  release(&bcache.lock[b->blockno % NBUCKET]);
}
//去除引用缓存块
void bunpin(struct buf *b)
{
  acquire(&bcache.lock[b->blockno % NBUCKET]);
  b->refcnt--;
  release(&bcache.lock[b->blockno % NBUCKET]);
}

